﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using System.Diagnostics;

namespace GameLibrary.Player
{
    using Map;
    using Settlement;
    using Unit;
    using Tile;
    using Exceptions;
    using Interfaces;
    using Events;

    /// <summary>
    /// Computer player
    /// </summary>
    [Serializable]
    public class Player:AbstractGameObject
    {

        #region variables

        #region map object

        /// <summary>
        /// Store all info objects
        /// </summary>
        public PlayerMap Map { get; private set; }

        /// <summary>
        /// Store city in control
        /// </summary>
        protected Dictionary<uint, Settlement> settlements = new Dictionary<uint, Settlement>();
        /// <summary>
        /// Store unit in control
        /// </summary>
        protected Dictionary<uint, Unit> units = new Dictionary<uint, Unit>();

        #endregion

        #region storage

        public long TotalIncome { get; protected set; }

        public long Storage { get; protected set; }

        #endregion

        #region ratios

        private Bias Bias { get; set; }

        #endregion

        #region units

        #region unit templates

        private Template soldierTemplate = Template.DefaultSoldier;
        private Template laborTemplate = Template.DefaultLabor;
        private Template scoutTemplate = Template.DefaultScout;

        private Template OthersBestSoliderTemplate = Template.DefaultSoldier;

        #endregion

        #region special units
        
        #region labor - for build village

        /// <summary>
        /// village builders
        /// </summary>
        private Dictionary<uint, Unit> labors = new Dictionary<uint, Unit>();

        #endregion

        #region recon -- for exploration

        /// <summary>
        /// scouts
        /// </summary>
        private Dictionary<uint, Unit> scouts = new Dictionary<uint, Unit>();

        #endregion

        #region soldier

        /// <summary>
        /// Army
        /// </summary>
        private Dictionary<uint, Unit> soldiers = new Dictionary<uint, Unit>();

        #endregion

        #endregion

        #endregion

        #region diplomatic relagionships

        protected Dictionary<uint,DiplomaticRelationshipType> relationships;

        #endregion

        #endregion

        protected GameManager GameManager
        {
            get;
            private set;
        }

        #region constructor

        public Player(
            GameManager gm,
            Position pos, 
            Bias bias,
            int initUnit = 2, 
            int initCity = 1)
        {
            this.GameManager = gm;

            this.Map = new PlayerMap(this.ID, MapHelper.FindRegion(pos));

            this.Bias = bias;

            //refresh units
            for (int i = 0; i < initUnit; i++)
            {
                Unit unit = new Unit(pos, this.ID, Template.DefaultLabor);
                this.Map.AddUnit(unit);
                this.units.Add(unit.ID,unit);                    
                this.labors.Add(unit.ID,unit);
                this.ConnectEvents(unit);
            }

            //refresh cities
            Settlement settlement = new Settlement(
                pos, 
                this.ID, 
                SettlementFlags.City, 
                this.Map.GetTileType(pos).BaseProduction
                );
            this.ConnectEvents(settlement);
            this.settlements.Add(settlement.ID, settlement);
            this.Map.AddSettlement(settlement);
            this.AddAdditionalUnits();            
        }

        /// <summary>
        /// Add additional units to each player 
        /// Aim: test battle system.
        /// </summary>
        protected void AddAdditionalUnits()
        {
            Template template = new Template(5, 0, 6, 5, 5, 3, 0, UnitActionFlags.All);
            List<Unit> additionals = new List<Unit>();
            for (int i = 0; i < 10; i++)
                additionals.Add(new Unit(this.settlements.Values.First().Location, this.ID, template));
            foreach (Unit u in additionals)
            {
                this.units.Add(u.ID, u);
                this.soldiers.Add(u.ID, u);
                this.Map.AddUnit(u);
            }
        }

        internal void SetRelationShip(
            Dictionary<uint, DiplomaticRelationshipType> relations)
        {
            this.relationships = relations;
        }

        #endregion

        #region events

        #region map object killed

        internal event EventHandler<MapObjectKilledEventArgs> MapObjectKilled;
        
        // send during next turn on each killed unit
        protected virtual void OnMapObjectKilled(IMapObject obj)
        {
            var h = this.MapObjectKilled;
            if (h != null)
                h(this, new Events.MapObjectKilledEventArgs(obj));
           // else
           //     throw new EventHandlerNullException("map object killed event handler null");
        }

        #endregion

        #region declear war

        public event EventHandler<Events.DeclearWarEventArgs> DeclearWar;
        protected virtual void OnDeclearWar(uint against)
        {
            EventHandler<Events.DeclearWarEventArgs> h = this.DeclearWar;
            if(h!=null)
                h(this,new Events.DeclearWarEventArgs(against,this.ID));
         //   else
         //       throw new EventHandlerNullException("declear war handler null");
        }

        #endregion

        #region new relationship

        public event EventHandler<Events.NewRelationshipEventArgs> NewRelationship;
        protected virtual void OnNewRelationship(uint newParty)
        {
            EventHandler<Events.NewRelationshipEventArgs> h = this.NewRelationship;
            if(h!=null)
                h(this,new Events.NewRelationshipEventArgs(newParty,this.ID));
         //   else
         //       throw new EventHandlerNullException("new relationship null");
        }

        #endregion

        #region player died

        public event EventHandler<PlayerDiedEventArgs> PlayerDied;
        protected virtual void OnPlayerDied()
        {
            EventHandler<PlayerDiedEventArgs> h = this.PlayerDied;
            if (h != null)
                h(this, new PlayerDiedEventArgs(this.ID));
            else
                throw new EventHandlerNullException("Player died handler null.");
        }

        #endregion

        #region event receiver

        private void BuildingLevelDecreased(object sender, Events.BuildingLevelDecreasedEventArgs e)
        {
            Settlement c = e.Settlement as Settlement;
            this.Map.RefreshSettlement(c);
        }
        private void OwnershipChanged(object sender, Events.OwnershipChangedEventArgs e)
        {

            if (e.OldOwner == this.ID)
            {
                this.DisconnectEvents(e.Obj);
                if (this.settlements.ContainsKey(e.Obj.ID))
                    this.settlements.Remove(e.Obj.ID);
            }

            if (e.NewOwner == this.ID)
            {
                if (this.settlements.ContainsKey(e.Obj.ID) == false)
                    this.settlements.Add(e.Obj.ID, e.Obj as Settlement);
            }

            this.Map.GetRegionInfo(e.Obj.Location).Refresh();
        }
        private void OwnershipChanging(object sender, Events.OwnershipChangingEventArgs e)
        {
            Settlement c = e.Obj as Settlement;
            if (c.OwnerID != this.ID)
                return;
            this.settlements.Remove(c.ID);
            if (c.Type == SettlementFlags.Village)
            {
                // get owner of c
                Settlement owner = this.settlements[c.SubordinateOf] as Settlement;
                owner.RemoveVillage(c);
            }
            else
            {
                var citiesInRegion = from city in this.Map.GetCityInARegion(MapHelper.FindRegion(c.Location))
                                     where city.Type == SettlementFlags.City // is city, which it can hold villages
                                     && city.OwnerID == this.ID // belong to this player
                                     select city;
                if (citiesInRegion.Count() == 0) // no other city in that region
                {
                    var villages = c.GetVillages();
                    Settlement v = villages.First();
                    v.ChangeToAnotherType(SettlementFlags.City);
                    foreach (var vil in from obj in villages
                                        where obj.ID != v.ID
                                        select obj)
                    {
                        v.AddVillage(vil);
                    }
                }
                else
                {
                    Settlement city = citiesInRegion.First();
                    foreach (var v in city.GetVillages())
                        city.AddVillage(v);
                }
            }
        }

        #endregion

        #region connect/disconnect events

        protected void ConnectEvents(IMapObjectWithEventHandler obj)
        {
            obj.OwnerChanging += this.OwnershipChanging;
            obj.OwnerChanged += this.OwnershipChanged;
            if (obj is Settlement)
            {
                Settlement settlement = obj as Settlement;
                settlement.BuildingLevelDecreased += this.BuildingLevelDecreased;
            }
        }
        protected void DisconnectEvents(IMapObjectWithEventHandler obj)
        {
            obj.OwnerChanged -= this.OwnershipChanged;
            obj.OwnerChanging -= this.OwnershipChanging;
            if (obj is Settlement)
            {
                Settlement settlement = obj as Settlement;
                settlement.BuildingLevelDecreased -= this.BuildingLevelDecreased;
            }
            if (obj is Unit)
            {
                // for future use
            }
        }
        #endregion

        #endregion

        #region check

        [Conditional("DEBUG")]
        private void CheckIsSettlement(IMapObject obj, string str)
        {
            if (!(obj is Settlement))
                throw new ShouldNotReachException(str + " \nObj should be settlement");
        }

        [Conditional("DEBUG")]
        private void CheckIsUnit(IMapObject obj, string str)
        {
            if (!(obj is Unit))
                throw new ShouldNotReachException(str + "\nObj should be Unit.");
        }

        [Conditional("DEBUG")]
        private void CheckZero(double i, string str)
        {
            if (i < 0)
                throw new ShouldBeMinZeroException(str + "\nShould minimal zero");
        }
        [Conditional("DEBUG")]
        private void CheckNull(IMapObject obj, string str)
        {
            if (obj == null)
                throw new ArgumentNullException(str + "\n Should not null");
        }
        #endregion

        #region build

        #region build army

        /// <summary>
        /// Build new units
        /// Add to this.units and map
        /// </summary>
        /// <param name="t"></param>
        /// <param name="pos"></param>
        /// <returns></returns>
        private Unit BuildArmy(Template t, Position pos)
        {
            Unit unit = new Unit(pos, this.ID, t);
            this.Map.AddUnit(unit);
            this.units.Add(unit.ID,unit);
            return unit;
        }

        #endregion

        #region settlement

        private void BuildSettlement(Position pos)
        {
            var cities = this.Map.GetCityInARegion(MapHelper.FindRegion(pos));

            // one region only have one city

            SettlementFlags flag = SettlementFlags.Village;
            if(cities == null)  // there are cities in that region
                flag = SettlementFlags.City;
            
            Settlement city = new Settlement(
                pos, 
                this.ID, 
                flag, 
                GameMap.UniqueInstance.GetTileType(pos).BaseProduction
                );
            
            if(flag == SettlementFlags.Village) // add all village to the single city 
                 cities.First().AddVillage(city);

            this.ConnectEvents(city);

            this.settlements.Add(city.ID,city);
            this.Map.AddSettlement(city);
        }



        private class SettlementProductivityComparer : IComparer<Settlement>
        {
            #region IComparer<City> Members

            public int Compare(Settlement x, Settlement y)
            {
                return y.Income.CompareTo(x.Income);
            }

            #endregion
        }

        #endregion

        #region road

        private void BuildRoad(double budget)
        {

            long totalSpending = 0;

            // get all roads
            List<Path> list = this.Map.GetAllPathes();

            // sort all roads by their total move cost
            // large first
            list.Sort(new PathCostComparer());

            // max cost upper limit for each item
            long maxCost = (long)(this.TotalIncome * PlayerHelper.MaxCostOfOneItemOfTotalIncome);
            
            // loop through each path
            foreach (var a in list)
            {
                var l = a.PositionList;

                // try to upgrade road for each position
                foreach (Position p in l)
                {
                    var settlement = (from s in this.settlements.Values
                                      where s.Location == p
                                      select s).First();

                    this.CheckIsSettlement(settlement, "In Player Build Road");

                    double buildCost = (settlement as Settlement).GetNextLevelBuildingCost(SettlementHelper.Road) * GameMap.UniqueInstance.GetTileType(p).BuildCostModifier;

                    if (buildCost < maxCost) // within max budget limit
                    {
                        totalSpending += (long)buildCost;
                        if (budget >= totalSpending)
                        {
                            (settlement as Settlement).AddBuilding(SettlementHelper.Road);
                        }
                        else
                        {
                            totalSpending -= (long)buildCost;
                            break;
                        }
                    }
                }
            }
            this.ChangeStorage(totalSpending);
        }

        private void ChangeStorage(long totalSpending)
        {
            this.Storage -= totalSpending;
            this.CheckZero(this.Storage, " Change storage this.storage.");
            this.CheckZero(totalSpending, " Change Storage totalSpending");
        }

        private class PathCostComparer : IComparer<Path>
        {
            #region IComparer<Path> Members

            public int Compare(Path x, Path y)
            {
                return y.TotalMoveCost.CompareTo(x.TotalMoveCost);
            }

            #endregion
        }
        #endregion

        #region settlement buildings

        /// <summary>
        /// Determine build what building in which city
        /// </summary>
        private void BuildBuildings()
        {
            #region budget

            double totalBudget = this.Storage * this.Bias.Build.Goods;
            // capacity
            double maxBudget = totalBudget * PlayerHelper.MaxCostOfOneItemOfTotalIncome;
            
            #endregion

            #region try build building for each settlement

            foreach (var city in from s in this.settlements.Values
                                       where (s as ISettlement).Type == SettlementFlags.City
                                       select s)
            {
                // check budget is still in limit
                if (totalBudget <= 1
                    || totalBudget <= maxBudget + 1)
                    break;

                // create item list
                List<Settlement> settlementList =
                    new List<Settlement> { city as Settlement };

                settlementList.AddRange((city as Settlement).GetVillages());

                // get knapsack inputs
                int budget = (int)maxBudget;
                int n, c;
                int[] profits, weights;
                AI.AIHelper.ChangeSettlementBuildingPairIntoKnapsackInput(
                    settlementList,
                    budget,
                    out n,
                    out c,
                    out profits,
                    out weights);

                // get knapsack result
                int totalProfit;
                int[] buildAtWhere;
                AI.Knapsack.Greedy.GetResult(
                    n, c, profits, weights,
                    out totalProfit,
                    out buildAtWhere);

                // build building in settlement
                // build in city
                if (buildAtWhere[0] == 1)
                {
                    budget -= settlementList[0].GetNextLevelBuildingCost(SettlementHelper.Factory);
                    settlementList[0].AddBuilding(SettlementHelper.Factory);
                }

                // build in village
                for (int i = 1; i < settlementList.Count; i++)
                {
                    if (buildAtWhere[i] == 1)
                    {
                        budget -= settlementList[i].GetNextLevelBuildingCost(SettlementHelper.Plant);
                        settlementList[i].AddBuilding(SettlementHelper.Plant);
                    }
                    if (budget < 1)
                        break;
                }

                totalBudget -= maxBudget + budget;
            }
            #endregion
        }
        #endregion

        #region labor

        /// <summary>
        /// Move labor from region which already finished building village 
        /// into regions which still building.
        /// Build labor if relocate is not enough.
        /// </summary>
        private void ArrangLabor(double budget)
        {
            #region get need

            // record which region need more labor
            HashSet<RegionInfo> regionNeedMoreLabor = new HashSet<RegionInfo>();

            // record labor which is not needed in its region
            HashSet<Unit> excessiveLabor = new HashSet<Unit>();

            // find which labor in which region
            Dictionary<RegionInfo, List<Unit>> regionLaborMap = this.GetUnitRegionMap(this.labors.Values);

            // find which region need labor and need how many
            foreach (var region in this.Map.GetAllRegionBelongToAPlayer(this.ID))
            {
                if (region.HaveFreeRegions == true)
                {
                    // need labor
                    if (regionLaborMap.ContainsKey(region) == false)
                    {
                        regionNeedMoreLabor.Add(region);
                    }
                }
                else
                {
                    if (regionLaborMap.ContainsKey(region) == true)
                        excessiveLabor.AddRange(regionLaborMap[region]);
                }
            }

            #endregion

            #region prepare input

            List<RegionInfo> regionList = regionNeedMoreLabor.ToList();
            List<Unit> unitList = excessiveLabor.ToList();

            int[] capacities = new int[regionList.Count];
            int[,] profits, weights;
            AI.AIHelper.ChangeUnitLocationPairIntoKnapsackInput(
                this.Map,
                regionList,
                unitList,
                out profits,
                out weights);

            for (int i = 0; i < capacities.GetLength(0); i++)
            {
                capacities[i] = PlayerHelper.MaxLaborPerCity
                    - regionLaborMap[regionList[i]].Count;

                this.CheckZero(capacities[i], "In Player build labor");
            }

            #endregion

            #region knapsack

            AI.Knapsack.YesNo yn;
            int totalProfit;
            int[] where;

            AI.Knapsack.MTHG.GetResult(
                unitList.Count, 
                regionList.Count,
                profits,
                weights,
                capacities,
                AI.Knapsack.MTHG.FeasiblityType.NegativeWeigitCapacityRatio,
                out totalProfit,
                out where,
                out yn
                );

            #endregion

            #region rearrange and build

            // rearrange
            for (int i = 0; i < unitList.Count; i++)
            {
                if (where[i] != 0)
                {
                    regionNeedMoreLabor.Remove(regionList[where[i]]);// arraged unit to region i
                    excessiveLabor.Remove(unitList[i]);  // this unit moved to region i in region list
                    
                    // move unit to region i
                    this.MoveUnit(unitList[i], regionList[where[i]].Start);
                }
            }

            //build
            if (regionNeedMoreLabor.Count > 0)
            {
                this.BuildLabor(regionNeedMoreLabor, budget);
            }

            #endregion
        }

        private void BuildLabor(HashSet<RegionInfo> regionNeedLabor, double budget)
        {
            long totalSpending = 0;

            foreach (var r in regionNeedLabor)
            {
                totalSpending += this.laborTemplate.Cost;

                if (budget > totalSpending)
                {
                    var city = r.GetSettlementByOwner(this.ID);
                    var unit = this.BuildArmy(this.laborTemplate, 
                                              city[0].Location);
                    this.labors.Add(unit.ID, unit);                                         
                }
                else
                {
                    totalSpending -= this.laborTemplate.Cost;
                    break;
                }
            }
        }
        #endregion

        #region scout

        private void ArrageScout(
            double budget, 
            AdjancencyList<RegionInfo,RegionInfo> border)
        {
            long totalSpending = 0;

            #region get scout region map

            Dictionary<RegionInfo, List<Unit>> scoutRegionMap = this.GetUnitRegionMap(this.scouts.Values);

            #endregion

            #region which region need scout

            var regionNeedScout = from r in border.Keys
                                  where scoutRegionMap.ContainsKey(r) == false
                                  || (scoutRegionMap[r].Count < border.Values(r).Count())
                                  select r;

            Dictionary<RegionInfo, int> regionNeeds = new Dictionary<RegionInfo, int>();
            
            foreach (var r in regionNeedScout)
            {
                int i = border.Values(r).Count() - scoutRegionMap[r].Count;
                regionNeeds.Add(r, i);
                this.CheckZero(i, "In Player Arrange Scout -- scouts less than need");
            }

            #endregion

            #region which region have more scout than needed

            var regionExcessiveWithScout =
                from r in border.Keys
                where
                    scoutRegionMap.ContainsKey(r) == true
                && border.Values(r).Count() < scoutRegionMap[r].Count
                select r;

            Dictionary<RegionInfo, int> regionExcessiveScout =
                new Dictionary<RegionInfo, int>();
            
            foreach (var r in regionExcessiveWithScout)
            {
                int i = scoutRegionMap[r].Count - border.Values(r).Count();
                regionExcessiveScout.Add(r, i);
                this.CheckZero(i, "In Player Arrange Scout -- scouts more than need");
            }

            #endregion

            #region prepare input

            List<RegionInfo> regionList = regionNeedScout.ToList();

            List<Unit> unitList = new List<Unit>();

            foreach (var r in regionExcessiveWithScout)
            {
                var set = scoutRegionMap[r];

                for (int i = 0; i < border.Values(r).Count(); i++)
                {
                    set.Remove(set.First());
                }
                unitList.AddRange(set);
            }

            int[,] profits, weights;
            int[] capacities = new int[regionList.Count];
            AI.AIHelper.ChangeUnitLocationPairIntoKnapsackInput(
                this.Map,
                regionList,
                unitList,
                out profits,
                out weights);

            for (int i = 0; i < capacities.GetLength(0); i++)
            {
                capacities[i] =
                    border.Values(regionList[i]).Count() -
                    scoutRegionMap[regionList[i]].Count;
                this.CheckZero(capacities[i], " In Player arrange scout");
            }

            #endregion 

            #region MTHG

            int[] where; // where item j put into
            int total;
            AI.Knapsack.YesNo feas;

            AI.Knapsack.MTHG.GetResult(
                unitList.Count,
                regionList.Count,
                profits,
                weights,
                capacities,
                AI.Knapsack.MTHG.FeasiblityType.ProfitWeightRatio,
                out total,
                out where,
                out feas
                );

            #endregion

            #region rearrange

            for (int i = 0; i < where.GetLength(0); i++)
            {
                if (where[i] != 0)
                {
                    regionNeeds[regionList[where[i]]]--;
                    this.MoveUnit(unitList[i], regionList[where[i]].Start);
                }
            }

            #endregion

            #region build

            var rest = from r in regionNeeds
                       where r.Value > 0
                       select r;

            foreach (var r in rest)
            {
                totalSpending += this.scoutTemplate.Cost;

                if (budget > totalSpending)
                {
                    var unit = this.BuildArmy(this.scoutTemplate, 
                                              r.Key.GetSettlements().ToList()[0].Location);
                    this.scouts.Add(unit.ID,unit);
                }
                else
                {
                    totalSpending -= this.scoutTemplate.Cost;
                    this.CheckZero(-budget, "Arrange Scout -- build budget");
                    break;
                }
            }
            this.ChangeStorage(totalSpending);
            #endregion
        }

        #endregion

        #region soldier

        private void BuildSoldier(double budget, AdjancencyList<RegionInfo,RegionInfo> border)
        {           
            #region get border have opponent

            // where unit should move to
            var borderHaveOpponent = new HashSet<RegionInfo>(
                from r in border.Keys
                where r.GetOwnerList().Any(n => this.relationships[n] == DiplomaticRelationshipType.War)
                || (from nb in border.Values(r)
                    select nb.GetOwnerList().Any(m => this.relationships[m] == DiplomaticRelationshipType.War))
                    .Any(o => o == true)
                select r
                );   
                            
            #endregion

            #region get border do not have opponent

            // where should have unit presents
            var borderDoNotHaveOpponent = new HashSet<RegionInfo>(
                border.Keys.Except(borderHaveOpponent)
                );

            #endregion 

            #region get fighting power along the border

            Dictionary<RegionInfo, long> fightingPowerAlongTheBorderRegions
                 = new Dictionary<RegionInfo, long>();

            foreach (var r in border.Keys)
            {
                List<RegionInfo> list = new List<RegionInfo>(border.Values(r));
                list.Add(r);

                fightingPowerAlongTheBorderRegions.Add(r, 0);

                foreach (var reg in list)
                    foreach (var u in reg.GetUnits())
                        if (this.labors.ContainsKey(u.ID) == true
                            || this.scouts.ContainsKey(u.ID) == true)
                            continue;
                        else
                            if (u.OwnerID == this.ID)
                                fightingPowerAlongTheBorderRegions[r] += u.Template.Cost;
                            else
                                fightingPowerAlongTheBorderRegions[r] -= u.Template.Cost;   
            }

            #endregion

            #region get regionlist

            HashSet<RegionInfo> rlist = new HashSet<RegionInfo>(borderHaveOpponent);

            var borderRegionDoNotHaveSufficientFightPower = 
                from r in borderDoNotHaveOpponent
                where fightingPowerAlongTheBorderRegions[r] < 0
                select r;

            rlist.AddRange(borderRegionDoNotHaveSufficientFightPower);

            List<RegionInfo> regionList = rlist.ToList();

            #endregion

            #region get unitlist

            Dictionary<RegionInfo, List<Unit>> unitPerRegion = this.GetUnitRegionMap(this.soldiers.Values);

            // where unit should move out from
            var innerRegion = new HashSet<RegionInfo> ( 
                              from r in this.Map.GetAllRegionBelongToAPlayer(this.ID)
                              where border.Keys.Contains(r) == false
                              select r
                              );

            var unitsInInnerRegion = 
                        from u in this.soldiers.Values
                        where innerRegion.Contains(this.Map.GetRegionInfo(u.Location)) == true
                        select u as Unit;

            HashSet<Unit> unitCanRedeploy = new HashSet<Unit>(unitsInInnerRegion);            

            foreach (var pair in fightingPowerAlongTheBorderRegions)
            {
                if (borderHaveOpponent.Contains(pair.Key) == true
                    || pair.Value < 0
                    )
                    continue;
                else
                {
                    // determine how many unit can move away
                    int number = (int)Math.Floor(pair.Value /(double) this.soldierTemplate.Cost);

                    this.CheckZero(number, "In Player arrange soldier -- get unit list");

                    // add those unit to unitCanRedeploy
                    for (int i = 0; i < number; i++)
                        unitCanRedeploy.Add(unitPerRegion[pair.Key][i]);
                }
            }

            List<Unit> unitList = unitCanRedeploy.ToList(); 
   
            #endregion
           
            #region prepare input

            int[,] profits;
            int[,] weights;

            AI.AIHelper.ChangeUnitLocationPairIntoKnapsackInput(
                this.Map,
                regionList,
                unitList,
                out profits,
                out weights
                );

            int[] capacities = new int[regionList.Count];

            for (int i = 0; i < capacities.GetLength(0); i++)
            {
                capacities[i] =
                    (int)Math.Ceiling(
                    fightingPowerAlongTheBorderRegions[regionList[i]]
                    / (double)this.soldierTemplate.Cost);

                this.CheckZero(capacities[i], "In Player arrange soldier -- prepare input");
            }

            #endregion

            #region knapsack

            int totalProfit;
            AI.Knapsack.YesNo feas;
            int[] where;

            AI.Knapsack.MTHG.GetResult(
                unitList.Count,
                regionList.Count,
                profits,
                weights,
                capacities,
                 AI.Knapsack.MTHG.FeasiblityType.ProfitWeightRatio,
                 out totalProfit,
                 out where,
                 out feas);

            #endregion

            #region rearrange

            for (int i = 0; i < where.GetLength(0); i++)
            {
                if (where[i] != 0)
                {
                    this.MoveUnit(unitList[i], regionList[where[i]].Start);
                    capacities[where[i]]--;
                    this.CheckZero(capacities[where[i]], " In player arrange soldier -- rearrange");
                }
            }

            #endregion

            #region build

            long totalSpending = 0;

            for (int i = 0; i < capacities.GetLength(0); i++)
            {
                bool flag = false;
                for (int j = 0; j < capacities[i]; j++)
                {
                    totalSpending += this.soldierTemplate.Cost;
                    if (budget > totalSpending)
                    {
                        var unit = this.BuildArmy(
                                this.soldierTemplate,
                                regionList[i].GetSettlementByOwner(this.ID)[0].Location
                                );
                        this.soldiers.Add(unit.ID, unit);
                    }
                    else
                    {
                        totalSpending -= this.soldierTemplate.Cost;

                        this.CheckZero(budget, "in player arrange soldier -- build");

                        flag = true;
                        break;
                    }
                }
                if (flag == true)
                    break;
            }
            this.ChangeStorage(totalSpending);
            #endregion
        }

        #endregion

        #endregion

        #region move unit

        protected void MoveUnit(Unit unit, Position pos)
        {
            Path path = this.Map.GetPath(unit.Location, pos);
            if (path.Fist == unit.Location)
                path.RemoveFirst();
            if (path.TotalMoveCost > unit.Current.AP)
            {
                // move to furthest position 
                double ap = unit.Current.AP;
                Position last = unit.Location;

                foreach (Position p in path.PositionList)
                {
                    double cost = this.Map.GetMoveCostOfAPosition(p);
                    if ((ap - cost) <= 0)
                    {
                        this.MoveUnit(unit, last);
                        break;
                    }
                    else
                    {
                        ap -= cost;
                        last = p;
                    }

                }
            }
            else
            {
                unit.SetLocation(pos);
                unit.Current.AP = unit.Current.AP - (float) path.TotalMoveCost;
            }
        }

        #endregion

        #region remove unit

        internal void RemoveUnit(Unit unit)
        {
            this.DisconnectEvents(unit);
            this.units.Remove(unit.ID);
            this.labors.Remove(unit.ID);
            this.scouts.Remove(unit.ID);
            this.soldiers.Remove(unit.ID);
            this.Map.RemoveUnit(unit); 
        }

        #endregion

        #region reconn

        /// <summary>
        /// Explore map find change in neighbor regions and knew new neighbors
        /// </summary>
        private void ExploreMap(AdjancencyList<RegionInfo,RegionInfo> border)
        {
            Dictionary<RegionInfo, List<Unit>> scoutPerRegion =
                this.GetUnitRegionMap(this.scouts.Values);

            foreach (var pair in scoutPerRegion)
            {
                List<RegionInfo> rl = new List<RegionInfo>(border.Values(pair.Key));
                for (int i = 0; i < pair.Value.Count && i < rl.Count; i++)
                {
                    rl[i].Refresh();

                    //get other player's template
                    var templates = from u in rl[i].GetUnits()
                                    where u.OwnerID != this.ID
                                    orderby u.Template.Cost descending
                                    select u.Template;                                    

                    //get most expansive template
                    // the more a template cost, the more fight ability it should have
                    // at least ai will do something like this
                    Template template = templates.First();

                    if (this.OthersBestSoliderTemplate.Cost < template.Cost)
                        this.OthersBestSoliderTemplate = template;

                    var playerIDList = this.GetPlayerIDListFromRegion(rl[i]);

                    this.MeedOtherPlayers(playerIDList);
                }
            }
        }

        private IEnumerable<uint> GetPlayerIDListFromRegion(RegionInfo region)
        {
            return region.GetOwnerList();
        }

        private void MeedOtherPlayers(IEnumerable<uint> playerIDList)
        {
            var newNeighbors = from n in playerIDList
                               where this.relationships.ContainsKey(n) == false
                                  && n != this.ID
                               select n;

            foreach (var id in newNeighbors)
            {
                this.OnNewRelationship(id);
            }
        }

        #endregion

        #region get unit-region map

        private Dictionary<RegionInfo, List<Unit>>
            GetUnitRegionMap(IEnumerable<IMapObject> list)
        {
            Dictionary<RegionInfo, List<Unit>> map = 
                new Dictionary<RegionInfo, List<Unit>>();

            foreach (Unit u in list)
            {
                RegionInfo r = this.Map.GetRegionInfo(u.Location);

                if (map.ContainsKey(r) == false)
                    map.Add(r, new List<Unit>());

                map[r].Add(u);
            }

            return map;
        }

        #endregion

        #region polic plan

        private void GetNewWar()
        {
            uint id = GameManager.HumPlayer.ID;

            if (this.relationships[id] != DiplomaticRelationshipType.War) // can alow a new war
            {
                this.OnDeclearWar(id);
            }
        }

        #endregion

        #region next turn

        #region settlement nextTurn

        /// <summary>
        /// Each settlement in control will porceed to next turn.
        /// Produce materials and give it to player.
        /// </summary>
        protected void SettlementNextTurn()
        {  
            this.TotalIncome = 0; // reset, only count one turn.

            foreach (Settlement c in this.settlements.Values)
            {
                if (c.Type == SettlementFlags.City
                    || c.SubordinateOf == this.ID
                    || c.SubordinateOf == 0)
                {
                    c.NextTurn();
                    this.TotalIncome += c.Production;
                    this.Storage += c.Storage;
                    c.SetStorage(0);                    
                }
            }

            foreach (Settlement s in this.settlements.Values)
                this.Map.RefreshSettlement(s);
        }

        #endregion

        #region unit next turn

        /// <summary>
        /// Each unit in control will reset their current value
        /// </summary>
        protected void UnitNextTurn()
        {
            foreach (Unit u in this.units.Values)
            {
                u.NextTurn();
                this.Map.RefreshUnit(u);
            }

        }

        #endregion

        #region build city

        /// <summary>
        /// Use labor to build village and city
        /// </summary>
        private void UseLaborBuildVillageAndCity()
        {
            throw new NotImplementedException();
        }

        #region delete
        /// <summary>
        /// this function need fix, reason cannot find whether it can reach a position or not.
        /// </summary>
        private void oldBuildsettlement()
        {
            Dictionary<RegionInfo, List<Unit>> laborRegionMap
                = this.GetUnitRegionMap(this.labors.Values);

            foreach (var r in laborRegionMap)
            {
                var availableList = r.Key.GetFreePosition();
                if (availableList.Count > 0)
                {
                    // get labor list for this region
                    Dictionary<uint, Position> units = new Dictionary<uint, Position>();
                    foreach (var u in r.Value)
                        units.Add(u.ID, u.Location);
                    // get where can build 
                    Dictionary<Position, TileType> land = this.Map.GetFreePosition(r.Key, r.Value.ToList());

                    var list = AI.SelectTheBestPositionToBuildVillageInACity.Select(
                        units,
                        land);

                    foreach (var pair in list)
                    {                        
                        var costMap = this.Map.GetRegionInfo(pair.Value).GetMoveCostMap(this.ID);
                        var unit = this.units[pair.Key];
                        Position unitLocation = new Position(unit.Location.X % GMHelper.RegionWidth,
                                                        unit.Location.Y % GMHelper.RegionHeight);
                        Position to = new Position(pair.Value.X % GMHelper.RegionWidth,
                            pair.Value.Y % GMHelper.RegionHeight);

                        var l = new AI.ShortestPath.AStar(costMap, unitLocation, to).GetResult();
                        Path p = new Path(l);
                        if (p.TotalMoveCost <= unit.Current.AP) // do not consider whether it can reach or not
                        {
                            (this.labors[pair.Key] as Unit).SetLocation(pair.Value);
                            this.BuildSettlement(pair.Value);
                            (this.labors[pair.Key] as Unit).Current.AP = 0;
                            this.Map.RefreshUnit(this.labors[pair.Key] as Unit);
                        }
                    }
                }
                else
                    continue;
            }
        }
        #endregion

        #endregion

        #region refresh region with city
        private IEnumerable<Position> GetRegionPositionsOfRegionWithCity()
        {
            HashSet<Position> set = new HashSet<Position>();
            foreach (var s in this.settlements.Values)
            {
                if(s.Type == SettlementFlags.City)
                    set.Add(MapHelper.FindRegion(s.Location));
            }
            return set;
        }

        internal void RefreshAllRegionsWithCity()
        {
            var regionPositions = this.GetRegionPositionsOfRegionWithCity();
            foreach (Position pos in regionPositions)
            {
                this.Map.RefreshRegion(pos);
                var playerIDList = this.GetPlayerIDListFromRegion(this.Map.GetRegionInfo(pos));
                this.MeedOtherPlayers(playerIDList);
            }
        }
        #endregion

        #region next turn

        internal virtual void NextTurn()
        {
            if (this.settlements.Count <= 0 // a player lost all its city cannot live for long
                && this.units.Count <= 0 // a player with no unit and no city cannot be alive.
                )
                this.OnPlayerDied();
            else
            {

                #region adjust ratio
                // not implement
                #endregion

                #region cities production and collect up

                this.SettlementNextTurn();

                #endregion

                #region units refresh units

                this.UnitNextTurn();

                #endregion

                #region refresh regions

                this.RefreshAllRegionsWithCity();

                #endregion

                #region get budget

                double scoutBudget = this.Storage * this.Bias.Build.Scout;
                double laborBudget = this.Storage * this.Bias.Build.Labor;
                double armBudget = this.Storage * this.Bias.Build.Armament;
                double buildingBudget = this.Storage * this.Bias.Build.Goods;
                double roadBudget = this.Storage * this.Bias.Build.Connection;

                #endregion

                #region get border
                // temporary
                var border = new List<RegionInfo>{
                    this.Map.GetRegionInfo(this.settlements.First().Value.Location) 
                                 };
                #endregion

                #region build scout

         //       this.ArrageScout(scoutBudget, border);

                #endregion

                #region reconn -- explore map

         //       this.ExploreMap(border);

                #endregion

                #region politic plan

               this.GetNewWar();

                #endregion

                #region SciTech develop
                /*     double total = this.BuildRatios.Armament + this.BuildRatios.Connection + this.BuildRatios.SciTechDevelopment;
            double sci = this.BuildRatios.SciTechDevelopment / total;
            GameManager.SciTechDev[this.ID].IncreaseSciencePoints(this.NationalStorage * sci * this.SciTechRatio.Consumer);// consumer see as sci
            GameManager.SciTechDev[this.ID].IncreaseTechnologyPoints(this.NationalStorage * sci * this.SciTechRatio.Capital); // capital see as tech
            this.NationalStorage *= (1 - sci);
        */
                #endregion

                #region connection plan -- build road, harbor and airport

           //     this.BuildRoad(roadBudget);

                #endregion

                #region generate new templates
/*
                this.soldierTemplate = 
                    new AI.EA.GetNewTemplate(
                        this.soldierTemplate,
                        this.OthersBestSoliderTemplate, 
                        (float)(armBudget * 0.1)
                        ).GetResult();
        */       
                #endregion

                #region build soldier

   //             this.BuildSoldier(armBudget, border);

                #endregion

                #region build labor

        //        this.ArrangLabor(laborBudget);

                #endregion

                #region build city

         //       this.UseLaborBuildVillageAndCity();

                #endregion

                #region Tactic plan on all front

                foreach (var r in border)
                {
                    HashSet<RegionInfo> regions = new HashSet<RegionInfo>();
                    regions.Add(r);               

                    // the three variables below store
                    // which units, settlements are effected in war and 
                    // which units are died
                    Dictionary<uint, UnitInfo> effectedUnits;
                    Dictionary<uint, SettlementInfo> effectedSettlements;
                    HashSet<uint> diedUnits;

                    // use LGP find local optimal solution of 
                    // how to arrange unit to achieve max performance
                    new AI.EA.TacticPlanner(this.ID,
                        this.Map.GetTileType,
                        this.Map.GetCurrentMapRegionInfo(regions),
                        regions,
                        r.GetMoveCostMap(),
                       false)// true)
                        .GetResult(
                        out effectedUnits,
                        out effectedSettlements,
                        out diedUnits);

                    foreach (var a in diedUnits)
                    {
                        var u = this.Map.GetUnitByID(a);

                        this.CheckIsUnit(u, "In Player NextTurn -- died units");

                        this.OnMapObjectKilled(u);
                        effectedUnits.Remove(a); // died units must be units effected by war
                    }

                    foreach (var u in effectedUnits.Keys)
                    {
                        Unit unit = this.Map.GetUnitByID(u);

                        this.CheckNull(unit, "in player next turn effected units all object should store in game map");

                        unit.Current = effectedUnits[u].Current;

                        if (unit.Location != effectedUnits[u].Location)
                            unit.SetLocation(effectedUnits[u].Location);
                    }

                    Dictionary<Position, HashSet<Settlement>> occupiedCities =
                        new Dictionary<Position, HashSet<Settlement>>();

                    foreach (var settlementID in effectedSettlements.Keys)
                    {
                        Settlement settlement = this.Map.GetSettlementByID(settlementID);

                        this.CheckNull(settlement, "In player next turn occupied cities all object should store in game map");

                        if (effectedSettlements[settlementID].OwnerID != settlement.OwnerID) // owner changed
                        {
                            settlement.SetOwnerID(effectedSettlements[settlementID].OwnerID);

                            Position p = MapHelper.FindRegion(settlement.Location);
                            if (occupiedCities.ContainsKey(p) == false)
                                occupiedCities.Add(p, new HashSet<Settlement>());
                            occupiedCities[p].Add(settlement);
                        }

                    }
                    this.ArrangeOccupiedCities(occupiedCities);
                }

                #endregion
               
            }
        }
        /// <summary>
        /// Change all captured settlement into village
        /// </summary>
        /// <param name="occupiedCities"></param>
        private void ArrangeOccupiedCities(
            Dictionary<Position, HashSet<Settlement>> occupiedCities)
        {
            foreach (var pair in occupiedCities)
            {
                var existingCity = (from c in
                                        this.Map.GetRegionInfo(pair.Key).GetSettlementByOwner(this.ID)
                                    where c.Type == SettlementFlags.City
                                    select c).ToList();

                Settlement city = this.settlements[existingCity.First().ID] as Settlement;

                foreach (var settlement in pair.Value)
                {
                    if (settlement.Type != SettlementFlags.Village) // is city
                        if (settlement.ID != city.ID) // not selected city
                            settlement.ChangeToAnotherType(SettlementFlags.Village);

                    city.AddVillage(settlement);

                    this.ConnectEvents(settlement);                    
                }
            }
        }

        #endregion

        #endregion
    }
}
